<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>3D Matrix Zeroing Visualization</title>
    <script src="https://cdn.tailwindcss.com"></script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/three.js/r128/three.min.js"></script>
    <script src="https://cdn.jsdelivr.net/npm/three@0.128.0/examples/js/controls/OrbitControls.min.js"></script>
    <style>
        #matrix-input {
            font-family: monospace;
        }
        .cell {
            transition: all 0.3s ease;
        }
        .highlight {
            box-shadow: 0 0 15px rgba(255, 255, 0, 0.8);
            transform: scale(1.05);
        }
        .zeroed {
            background-color: #f87171 !important;
        }
        .marked-row {
            background-color: rgba(252, 211, 77, 0.3) !important;
        }
        .marked-col {
            background-color: rgba(52, 211, 153, 0.3) !important;
        }
        #canvas-container {
            position: relative;
            width: 100%;
            height: 500px;
            background-color: #1f2937;
            border-radius: 0.5rem;
            overflow: hidden;
        }
        .control-btn {
            transition: all 0.2s ease;
        }
        .control-btn:hover {
            transform: translateY(-2px);
        }
    </style>
</head>
<body class="bg-gray-900 text-gray-100 min-h-screen">
    <div class="container mx-auto px-4 py-8">
        <h1 class="text-4xl font-bold text-center mb-8 text-blue-400">3D Matrix Zeroing Visualization</h1>
        
        <div class="grid grid-cols-1 lg:grid-cols-3 gap-8 mb-8">
            <div class="bg-gray-800 p-6 rounded-lg shadow-lg">
                <h2 class="text-2xl font-semibold mb-4 text-green-400">Algorithm Explanation</h2>
                <p class="mb-4">This visualization demonstrates the "Set Matrix Zeroes" algorithm which:</p>
                <ol class="list-decimal pl-5 space-y-2">
                    <li>Scans the matrix to find all zeros</li>
                    <li>Marks the corresponding rows and columns</li>
                    <li>Sets all elements in marked rows/columns to zero</li>
                </ol>
                <div class="mt-4 p-4 bg-gray-700 rounded">
                    <p class="text-yellow-400 font-mono">Time Complexity: O(m×n)</p>
                    <p class="text-yellow-400 font-mono">Space Complexity: O(m+n)</p>
                </div>
            </div>
            
            <div class="bg-gray-800 p-6 rounded-lg shadow-lg">
                <h2 class="text-2xl font-semibold mb-4 text-purple-400">Matrix Input</h2>
                <div class="mb-4">
                    <label for="matrix-input" class="block mb-2">Enter matrix (JSON format):</label>
                    <textarea id="matrix-input" class="w-full h-32 p-2 bg-gray-700 rounded font-mono">[[1,1,1],[1,0,1],[1,1,1]]</textarea>
                </div>
                <button id="update-matrix-btn" class="w-full py-2 bg-blue-600 hover:bg-blue-700 rounded control-btn">
                    Update Matrix
                </button>
            </div>
            
            <div class="bg-gray-800 p-6 rounded-lg shadow-lg">
                <h2 class="text-2xl font-semibold mb-4 text-red-400">Controls</h2>
                <div class="grid grid-cols-3 gap-2 mb-4">
                    <button id="play-btn" class="py-2 bg-green-600 hover:bg-green-700 rounded control-btn">
                        ▶ Play
                    </button>
                    <button id="pause-btn" class="py-2 bg-yellow-600 hover:bg-yellow-700 rounded control-btn">
                        ⏸ Pause
                    </button>
                    <button id="reset-btn" class="py-2 bg-red-600 hover:bg-red-700 rounded control-btn">
                        ↻ Reset
                    </button>
                </div>
                <div class="mb-4">
                    <label for="speed-slider" class="block mb-2">Animation Speed:</label>
                    <input type="range" id="speed-slider" min="0.5" max="5" step="0.5" value="1" class="w-full">
                    <div class="flex justify-between text-xs text-gray-400">
                        <span>Slow</span>
                        <span>Fast</span>
                    </div>
                </div>
                <div class="mt-4 p-3 bg-gray-700 rounded">
                    <p class="text-center" id="status-display">Ready</p>
                </div>
            </div>
        </div>
        
        <div id="canvas-container">
            <div id="legend" class="absolute bottom-4 left-4 bg-gray-800 bg-opacity-80 p-2 rounded text-sm">
                <div class="flex items-center mb-1">
                    <div class="w-4 h-4 bg-blue-500 mr-2"></div>
                    <span>Original Value</span>
                </div>
                <div class="flex items-center mb-1">
                    <div class="w-4 h-4 bg-yellow-500 mr-2"></div>
                    <span>Marked Row</span>
                </div>
                <div class="flex items-center mb-1">
                    <div class="w-4 h-4 bg-emerald-500 mr-2"></div>
                    <span>Marked Column</span>
                </div>
                <div class="flex items-center">
                    <div class="w-4 h-4 bg-red-500 mr-2"></div>
                    <span>Zeroed Cell</span>
                </div>
            </div>
        </div>
        
        <div class="mt-8 bg-gray-800 p-6 rounded-lg shadow-lg">
            <h2 class="text-2xl font-semibold mb-4 text-blue-400">Result</h2>
            <div id="result-display" class="font-mono bg-gray-700 p-4 rounded">
                Result will appear here after animation completes
            </div>
        </div>
    </div>

    <script>
        // Global variables
        let scene, camera, renderer, cubes = [], controls;
        let animationId = null;
        let animationSpeed = 1;
        let animationState = 'idle'; // 'idle', 'playing', 'paused'
        let currentStep = 0;
        let totalSteps = 0;
        let matrix = [[1,1,1],[1,0,1],[1,1,1]];
        let originalMatrix = [];
        let rowMarkers = [];
        let colMarkers = [];
        
        // Initialize Three.js scene
        function initScene() {
            // Create scene
            scene = new THREE.Scene();
            scene.background = new THREE.Color(0x1f2937);
            
            // Create camera
            camera = new THREE.PerspectiveCamera(75, document.getElementById('canvas-container').clientWidth / document.getElementById('canvas-container').clientHeight, 0.1, 1000);
            camera.position.set(5, 5, 10);
            camera.lookAt(0, 0, 0);
            
            // Create renderer
            renderer = new THREE.WebGLRenderer({ antialias: true });
            renderer.setSize(document.getElementById('canvas-container').clientWidth, document.getElementById('canvas-container').clientHeight);
            document.getElementById('canvas-container').appendChild(renderer.domElement);
            
            // Add lights
            const ambientLight = new THREE.AmbientLight(0x404040);
            scene.add(ambientLight);
            
            const directionalLight = new THREE.DirectionalLight(0xffffff, 1);
            directionalLight.position.set(1, 1, 1);
            scene.add(directionalLight);
            
            // Add orbit controls
            controls = new THREE.OrbitControls(camera, renderer.domElement);
            controls.enableDamping = true;
            controls.dampingFactor = 0.05;
            
            // Handle window resize
            window.addEventListener('resize', () => {
                camera.aspect = document.getElementById('canvas-container').clientWidth / document.getElementById('canvas-container').clientHeight;
                camera.updateProjectionMatrix();
                renderer.setSize(document.getElementById('canvas-container').clientWidth, document.getElementById('canvas-container').clientHeight);
            });
            
            // Animation loop
            function animate() {
                animationId = requestAnimationFrame(animate);
                controls.update();
                renderer.render(scene, camera);
            }
            
            animate();
            
            // Initialize the matrix visualization
            updateMatrixVisualization();
        }
        
        // Create or update the matrix visualization
        function updateMatrixVisualization() {
            // Clear existing cubes
            cubes.forEach(cube => {
                scene.remove(cube);
            });
            cubes = [];
            
            const m = matrix.length;
            const n = matrix[0].length;
            
            // Calculate spacing between cubes
            const spacing = 1.5;
            const startX = -((n - 1) * spacing) / 2;
            const startY = ((m - 1) * spacing) / 2;
            
            // Create cubes for each matrix element
            for (let i = 0; i < m; i++) {
                for (let j = 0; j < n; j++) {
                    const value = matrix[i][j];
                    const color = getCellColor(i, j, value);
                    
                    const geometry = new THREE.BoxGeometry(1, 1, 1);
                    const material = new THREE.MeshPhongMaterial({ color: color });
                    const cube = new THREE.Mesh(geometry, material);
                    
                    cube.position.x = startX + j * spacing;
                    cube.position.y = startY - i * spacing;
                    cube.position.z = 0;
                    
                    // Store matrix indices as properties
                    cube.userData = { row: i, col: j, value: value };
                    
                    scene.add(cube);
                    cubes.push(cube);
                }
            }
            
            // Add labels for each cube
            addValueLabels();
        }
        
        // Get color for cell based on its state
        function getCellColor(row, col, value) {
            if (currentStep >= totalSteps - 1 && (rowMarkers[row] || colMarkers[col])) {
                return 0xf87171; // red for zeroed cells
            } else if (rowMarkers[row]) {
                return 0xfbbf24; // yellow for marked rows
            } else if (colMarkers[col]) {
                return 0x34d399; // emerald for marked columns
            } else {
                return value === 0 ? 0xef4444 : 0x3b82f6; // red for 0, blue for others
            }
        }
        
        // Add value labels to cubes
        function addValueLabels() {
            // Remove existing labels if any
            scene.children.forEach(child => {
                if (child.userData.isLabel) {
                    scene.remove(child);
                }
            });
            
            const loader = new THREE.TextureLoader();
            cubes.forEach(cube => {
                const { row, col, value } = cube.userData;
                
                // Create canvas for text
                const canvas = document.createElement('canvas');
                canvas.width = 64;
                canvas.height = 64;
                const context = canvas.getContext('2d');
                context.fillStyle = '#ffffff';
                context.font = '24px Arial';
                context.textAlign = 'center';
                context.textBaseline = 'middle';
                context.fillText(value.toString(), 32, 32);
                
                // Create texture from canvas
                const texture = new THREE.CanvasTexture(canvas);
                
                // Create sprite material
                const spriteMaterial = new THREE.SpriteMaterial({ 
                    map: texture,
                    transparent: true,
                    depthTest: false
                });
                
                // Create sprite
                const sprite = new THREE.Sprite(spriteMaterial);
                sprite.position.copy(cube.position);
                sprite.position.z = 0.6; // Place slightly in front of the cube
                sprite.scale.set(0.5, 0.5, 0.5);
                sprite.userData = { isLabel: true };
                
                scene.add(sprite);
            });
        }
        
        // Highlight a specific cell
        function highlightCell(row, col, highlight = true) {
            const cube = cubes.find(c => c.userData.row === row && c.userData.col === col);
            if (cube) {
                if (highlight) {
                    cube.scale.set(1.2, 1.2, 1.2);
                    cube.material.emissive.setHex(0xffff00);
                    cube.material.emissiveIntensity = 0.5;
                } else {
                    cube.scale.set(1, 1, 1);
                    cube.material.emissive.setHex(0x000000);
                    cube.material.emissiveIntensity = 0;
                }
            }
        }
        
        // Animate the algorithm steps
        async function animateAlgorithm() {
            if (animationState !== 'playing') return;
            
            const m = matrix.length;
            const n = matrix[0].length;
            
            // Step 1: Mark rows and columns containing zeros
            if (currentStep < m * n) {
                const i = Math.floor(currentStep / n);
                const j = currentStep % n;
                
                // Highlight current cell
                highlightCell(i, j);
                
                // If cell is zero, mark its row and column
                if (matrix[i][j] === 0) {
                    rowMarkers[i] = true;
                    colMarkers[j] = true;
                    
                    // Update visualization to show marked rows/columns
                    updateMatrixVisualization();
                    
                    // Add slight delay for visualization
                    await sleep(500 / animationSpeed);
                }
                
                // Unhighlight after processing
                highlightCell(i, j, false);
                
                currentStep++;
                updateStatus(`Scanning cell (${i}, ${j})`);
            } 
            // Step 2: Zero out marked rows and columns
            else if (currentStep < m * n * 2) {
                const step = currentStep - m * n;
                const i = Math.floor(step / n);
                const j = step % n;
                
                // Highlight current cell
                highlightCell(i, j);
                
                // If cell is in a marked row or column, zero it
                if (rowMarkers[i] || colMarkers[j]) {
                    // Update visualization to show zeroed cells
                    updateMatrixVisualization();
                    
                    // Add slight delay for visualization
                    await sleep(500 / animationSpeed);
                }
                
                // Unhighlight after processing
                highlightCell(i, j, false);
                
                currentStep++;
                updateStatus(`Zeroing cell (${i}, ${j})`);
            } 
            // Animation complete
            else {
                animationState = 'idle';
                updateStatus('Animation complete');
                showResult();
                return;
            }
            
            // Continue animation
            setTimeout(animateAlgorithm, 100 / animationSpeed);
        }
        
        // Show final result
        function showResult() {
            const result = JSON.stringify(matrix.map((row, i) => 
                row.map((val, j) => rowMarkers[i] || colMarkers[j] ? 0 : originalMatrix[i][j])
            ), null, 2);
            
            document.getElementById('result-display').textContent = result;
        }
        
        // Reset animation
        function resetAnimation() {
            // Cancel any ongoing animation
            if (animationId) {
                cancelAnimationFrame(animationId);
                animationId = null;
            }
            
            // Reset state
            animationState = 'idle';
            currentStep = 0;
            
            // Reset row and column markers
            rowMarkers = new Array(matrix.length).fill(false);
            colMarkers = new Array(matrix[0].length).fill(false);
            
            // Reset visualization
            updateMatrixVisualization();
            updateStatus('Ready');
            document.getElementById('result-display').textContent = 'Result will appear here after animation completes';
        }
        
        // Start animation
        function startAnimation() {
            if (animationState === 'playing') return;
            
            // Make a copy of the original matrix
            originalMatrix = JSON.parse(JSON.stringify(matrix));
            
            // Initialize row and column markers
            rowMarkers = new Array(matrix.length).fill(false);
            colMarkers = new Array(matrix[0].length).fill(false);
            
            // Calculate total steps (scan + zero)
            totalSteps = matrix.length * matrix[0].length * 2;
            
            // Set state and start animation
            animationState = 'playing';
            currentStep = 0;
            updateStatus('Animation started');
            animateAlgorithm();
        }
        
        // Pause animation
        function pauseAnimation() {
            if (animationState === 'playing') {
                animationState = 'paused';
                updateStatus('Animation paused');
            }
        }
        
        // Resume animation
        function resumeAnimation() {
            if (animationState === 'paused') {
                animationState = 'playing';
                updateStatus('Animation resumed');
                animateAlgorithm();
            }
        }
        
        // Update status display
        function updateStatus(message) {
            document.getElementById('status-display').textContent = message;
        }
        
        // Helper function for delays
        function sleep(ms) {
            return new Promise(resolve => setTimeout(resolve, ms));
        }
        
        // Initialize when DOM is loaded
        document.addEventListener('DOMContentLoaded', () => {
            // Initialize 3D scene
            initScene();
            
            // Set up event listeners
            document.getElementById('play-btn').addEventListener('click', startAnimation);
            document.getElementById('pause-btn').addEventListener('click', pauseAnimation);
            document.getElementById('reset-btn').addEventListener('click', resetAnimation);
            document.getElementById('speed-slider').addEventListener('input', (e) => {
                animationSpeed = parseFloat(e.target.value);
            });
            
            document.getElementById('update-matrix-btn').addEventListener('click', () => {
                try {
                    const input = document.getElementById('matrix-input').value.trim();
                    const newMatrix = JSON.parse(input);
                    
                    // Validate matrix
                    if (!Array.isArray(newMatrix) || newMatrix.length === 0 || 
                        !Array.isArray(newMatrix[0]) || newMatrix[0].length === 0) {
                        throw new Error('Invalid matrix format');
                    }
                    
                    // Check all rows have same length
                    const rowLength = newMatrix[0].length;
                    for (let row of newMatrix) {
                        if (!Array.isArray(row) || row.length !== rowLength) {
                            throw new Error('All rows must have the same length');
                        }
                    }
                    
                    // Update matrix and reset visualization
                    matrix = newMatrix;
                    resetAnimation();
                } catch (error) {
                    alert('Error parsing matrix: ' + error.message);
                    console.error(error);
                }
            });
        });
    </script>
</body>
</html>